1. Field of the Invention
The present invention relates to a synchronization apparatus in a Viterbi decoder, and more particularly to synchronization method and apparatus for performing a fast and effective synchronization during Viterbi decoding of convolutional codes punctured in a predetermined puncturing pattern.
2. Description of the Prior Art
In general, Viterbi algorithm is used as a practical and efficient method for a maximum-likelihood decoding of convolutional codes. In the Viterbi algorithm, path distances of two different paths which meet at an arbitrary state are compared by using a trellis diagram. By the comparison, the path with a shorter distance, namely a path of the lowest error generation probability, is selected as a survivor path. A Viterbi decoder using the Viterbi algorithm is, for example, used for error correction in satellite communication systems, since the decoder has a high random error correction capability.
In digital communication systems, the punctured coding technique is used to obtain a high transmission rate for channels having limited band width. The codes punctured with this technique having code rates of the form n/(n+1) can be processed by a rate 1/2 Viterbi decoder. Prior to transmission, punctured codes are generated by deleting certain codewords from the rate 1/2 convolutionally encoded data stream. This increases the code rate of the Forward Error Correction (FEC) system. The code rate refers to the ratio of information bit rate to the rate of transmitted codewords.
In a transmission channel using a Quadrature Phase Shift Keying (QPSK) modulation, a rate 3/4 (R=3/4) encoding system using the punctured coding technique will be proposed as an example, here. Each transmission symbol, D(n) is comprised of two codewords, C0(n) and C1(n). In three encoded symbols from a code rate 1/2 convolutional encoder, prior to transmission over the channel, two of every six codewords punctured in a specific pattern are not transmitted. For example, according to corresponding puncture patterns, codewords C0(1) and C1(1) of the symbol D(1) are transmitted as a single QPSK symbol without modification, and codewords C0(2) and C1(3) of the symbols D(2) and D(3), respectively, are punctured. The remaining codewords C1(2) and C0(3) of the symbols D(2) and D(3), respectively, are formed into a new symbol for transmission. As a result, a total of four codewords are transmitted for information bits D(1), D(2), and D(3), resulting in a rate 3/4 code.
The following table 1 represents an example of the puncturing patterns for the five code rates defined by European Digital Video Broadcasting Standard.
TABLE 1 ______________________________________ code rate puncturing pattern transmitted sequence ______________________________________ 1/2 X:1 x1 y1 Y:1 2/3 X:10 x1 y1 y2 Y:11 3/4 X:101 x1 yl y2 x3 Y:110 5/6 X:10101 x1 y1 y2 x3 y4 x5 Y:11010 7/8 X:1000101 x1 y1 y2 y3 y4 x5 y6 x7 Y:1111010 ______________________________________
The symbols received at the decoder are reordered into the original codeword by replacing the codewords deleted by the puncturing circuit at the encoder with the "null" or "erased" codewords. Namely, a punctured encoding process will only be effective if the encoder puncture pattern is aligned with the decoder null-insertion sequence, otherwise, the problem of synchronization occurs. At the receiving node of the digital communication system using the punctured coding technique, first, a code rate of the transmitted symbols should be grasped, second, the synchronization is performed when depuncturing according to the puncturing pattern of transmitted symbols. For these, FEC chips made in Europe or U.S.A. are equipped with a function of automatic depuncturing, however, some are equipped with a manual code rate selecting function as well as the automatic depuncturing function, since the automatic depuncturing function does not always operate properly.
FIG. 1 shows a block diagram of a Viterbi decoder comprising a conventional synchronization circuit. The Viterbi decoder comprises a phase rotator 100, a depuncturing unit 102, a Viterbi decoding unit 104, a bit error counter 106, a channel data bit counter 108, and a decision unit 110.
In FIG. 1, the phase rotator 100 receives in-phase I-channel data and quadrature phase Q-channel data demodulated from QPSK demodulator (not shown), rotates their phases according to a phase rotating signal from the decision unit 110, and outputs I and Q-channel data with rotated phase to the depuncturing unit 102.
The depuncturing unit 102 performs depuncturing for the signals outputted from the phase rotator 100. At this time, the depuncturing corresponding to the code rate of the transmitting node should be performed. Additionally, the depuncturing unit 102 changes the puncturing pattern according to a pattern changing signal from the decision unit 110 to perform the depuncturing. Data depunctured in the depuncturing unit 102 are inputted into the Viterbi decoding unit 104 to be Viterbi-decoded. The decoded data are then inputted into the bit error counter 106.
The bit error counter 106 convolutionally encodes the decoded data from the Viterbi decoding unit 104, again. Then, the bit error counter 106 compares the obtained convolutionally encoded data with the depunctured data from the depuncturing unit 102, and counts the obtained bit error. The counted value from the bit error counter 106 is inputted into the decision unit 110 as a channel error bit rate (CEBR) signal.
The channel data bit counter 108 receives one of the I-channel data and the Q-channel data to count channel data bit with respect to a predetermined period and outputs the counted value to the decision unit 110 as a channel data bit rate (CDBR) signal.
The decision unit 110 is reset by a reset signal of an external mi-com (not shown). Next, to find the code rate of transmitted convolutional codes, the decision unit 110, after setting the code rate range from 1/2 to 7/8, sequentially performs a code rate detecting operation for the five code rates 1/2, 2/3, 3/4, 5/6, and 7/8. In this process. the CDBR from the channel data bit counter 108 is compared to a reference CDBR. If the CDBR concurs with the reference CDBR, the CBER from the error bit counter 106 is compared to a predetermined CBER threshold value corresponding to each code rate. The CBER threshold value corresponding to each code rate is determined through a computer simulation, under the channel environment considering the satellite power, the antenna size and the weather conditions. If the CBER is less than the predetermined CBER threshold value, the decision unit 110 outputs a sync signal to the depuncturing unit 102. Otherwise, the decision unit 110 outputs a phase rotating signal and a pattern changing signal to the phase rotator 100 and the depuncturing unit 102, respectively. And, the decision unit 110 outputs a flag-sync signal external to the FEC chip and Reed-Solomon decoder (not shown).
On the basis of European Digital Video Broadcasting Standard, there are five code rates 1/2, 2/3, 3/4, 5/6, and 7/8 such as shown in the table 1. Accordingly, there are as much puncturing patterns as each code rate's numerator. For example, there are seven kinds of puncturing patterns when the code rate is 7/8, and five kinds when the rate is 5/6. Namely, since five kinds of code rates and puncturing patterns corresponding to each code rate's numerator exist, the automatic depuncturing apparatus should detect the code rate of currently-received data as well as the puncturing pattern for the detected code rate. In addition, to decide whether the phase is true or false, namely to synchronize with the phase, the automatic depuncturing apparatus should detect the phase synchronization for both cases.
However, since the conventional synchronization method and apparatus having the above automatic depuncturing function detects the code rate, the puncturing pattern, and the phase synchronization through trial & error process using ascending order or descending order, the effective synchronization cannot be performed. Namely, first of all, from the code rate 1/2, the pattern synchronization and the phase synchronization are analyzed by comparing the measured CBER to the threshold value of CBER. If the measured CBER is larger than the threshold CBER, the trial & error process continues for each pattern synchronization and phase synchronization of the code rate 2/3. Similarly, the process is repeated for the code rates 3/4, 5/6, and 7/8. The total number of steps required for synchronization, in the worst case, is 36 steps: i.e., 36=2.times.1 (when the code rate is 1/2)+2.times.2 (when the code rate is 2/3)+2.times.3 (when the code rate is 3/4)+2.times.5 (when the code rate is 5/6)+2.times.7 (when the code rate is 7/8). Hence, the trial & error process consumes considerable amount of time for accurate synchronization. More particularly, since the synchronization cannot be performed properly in a unfavorable channel environment, and the above entire synchronizing process is performed for each channels, which are changed frequently by a remote control system, the conventional synchronization method and apparatus are ineffective for performing fast synchronization.